Complex integrated circuits (ICs) are typically designed using a CAD system. The CAD system allows the user to design a circuit using pre-designed circuit building blocks from a library. One basic structure frequently designed using logic synthesis tools is an adder for adding binary numbers of any bit width. Common adder designs which would be incorporated into the library are ripple adders, carry-select adders, and carry look-ahead adders. Subsets of adders include comparators (only determines carry) and counters (increments by 1).
Equation 1 below is the well known equation for generating a sum bit Si for two binary numbers X.sub.i and Y.sub.i, for the bit position i, where C.sub.i-1 is the carry bit from the next lower significant bit position. EQU S.sub.i =(X.sub.i Y.sub.i) C.sub.i-1 Eq. 1
In this disclosure, the symbol " " is a logical exclusive OR (XOR), the symbol "*" is a logical AND, and the symbol "+" is a logical OR.
The equations presented herein are also shown or described in the book Computer Architecture: A Quantitative Approach, Appendix A, by David A. Patterson and John L. Hennessy, ISBN 1-55860-069-8, incorporated herein by reference.
Ripple adders are so named because the carry bit for a pair of binary numbers must be calculated before the sum of the next higher significant bits can be calculated. This delay in generating each carry bit ripples along the ripple adder so that the total delay is proportional to the width of the binary numbers to be added.
Ripple adders are slow, but simple, and take up relatively little silicon surface area.
A more complex adder structure which uses a greater amount of silicon surface area than the ripple adder for the same adder bit width is shown in FIG. 1 and is generally called a carry select adder is approximately proportional to the square root of the bit width, assuming uniform input signal arrival times and optimal stage lengths.
FIG. 1 shows a 5-bit carry select adder having two stages 3 and 4, stage 3 being comprised of two adders 6 and 7, and stage 4 being comprised of three adders 8, 9, and 10. The outputs of the last adder in a stage (adders 7 and 10) are applied to a multiplexer 12 or 14.
Both stages 3 and 4 of FIG. 1 begin computing in parallel, with the adders in each stage computing in series. The final sum bits (S0-S4) and carry bit (C.sub.out) are not valid until the carry input (C.sub.in0 and C.sub.in1) saves for each stage. Two possible sum bits for each adder 6-10 and two possible carry bits for each adder 6-10 are calculated before the carry input bit arrives for the stage. The carry input (C.sub.in0) for stage 3 can be set to zero if there is no carry into stage 3. Stage 4 cannot provide its final sum bits and carry output (C.sub.out) bit until stage 3 has output its carry bit (C.sub.in1) by the appropriate control of multiplexer 12. Hence, the delay by stage 3 in calculating the carry bit C.sub.in1 is added to the accumulated delays by the multiplexers when calculating the final carry bit C.sub.out. Such delay, however, is much less than the conventional ripple adder.
The various outputs of each adder 6-10 and multiplexers 12 and 14 are calculated as expressed in the well-known equations below.
The sum for bit i in stage k can be computed from: EQU s1.sub.k,i =(X.sub.k,i Y.sub.k,i) cl.sub.k,i-1 Eq. 2
(final sum bit in stage k, bit i, for carry in=1) EQU s0.sub.k,i =(X.sub.k,i Y.sub.k,i) c0.sub.k,i-1 Eq. 3 PA1 (final sum bit in stage k, bit i, for carry in=0) PA1 (carry bit for stage k, bit i, for carry in=1) EQU C0.sub.k,i =(X.sub.k,i *Y.sub.k,i)+c0.sub.k,i-1 *(X.sub.k,i +Y.sub.k,i)Eq. 5 PA1 (carry bit for stage k, bit i, for carry in=0) PA1 (sum in stage k, bit i, as selected by the carry in for that stage)
The carry bit output (c0, c1) from each adder 6-10 can be computed from: EQU c1.sub.k,i =(X.sub.k,i * Y.sub.k,i)+c1.sub.k,i-1 *(X.sub.k,i +Y.sub.k,i)Eq. 4
The carry bits applied to the first adder 6 and 8 in each stage are fixed as: EQU c1.sub.k,-1 =1(input bit c1) Eq. 6 EQU c0.sub.k,-1 =0(input bit c0) Eq. 7
The final sum output (S0-S4) selected for each adder 6-10 based on the carry-in bit (C.sub.in) for that stage is follows: EQU S.sub.k,i =s1.sub.k,i if C.sub.in =1 Eq. 8 EQU s0.sub.k,i if C.sub.in =0
The output carry bit from a stage k is as follows: EQU C.sub.k =cl.sub.k,n-1 if C.sub.in =1 Eq. 9 EQU C0.sub.k,n-1 if C.sub.in =0
(carry out from stage k with n bits, as selected by the carry in (e.g., C.sub.in0 or C.sub.in1) for that stage)
The equations above are presented in a summary fashion and would be readily understood, and already known, to those skilled in the art. Additional detail is presented in the book Computer Architecture: A Quantitative Approach, previously mentioned.
In a carry look-ahead adder (CLA), the carry signals for each bit are computed in parallel in a tree structure. One type of CLA is shown in FIG. 2. The tree structure can be made to have more logic per stage (bigger), but fewer stages (faster), resulting in a bigger, faster adder, or less logic per stage (smaller), but more stages (slower) for a smaller, slower adder. A CLA should be designed to compute the carries (C.sub.i) for each bit position as fast as possible given the amount of silicon surface area allocated. Usually, a tree is built with log.sub.2 (n) stages, where n is the bit width of the numbers to be added. If n is not a power of 2, then the number of stages is log.sub.2 of the next higher power of 2. At each stage (k), the CLA tree computes a generate signal (G) and a propagate signal (P) for bit i, where: EQU G.sub.k+1,i =G.sub.k,i +(P.sub.k,i *G.sub.k,i-2.sup.k) Eq. 10 EQU P.sub.k+1,i =P.sub.k,i *P.sub.k,i-2.sup.k Eq. 11
Each block 22 making up the tree performs the following logical operations on its inputs to generate G.sub.out and P.sub.out : EQU G.sub.out =G.sub.in +(P.sub.in * G0.sub.in) Eq. 12 EQU P.sub.out =P.sub.in *P0.sub.in Eq. 13
The G signals indicate that there will definitely be a carry bit at bit i; the P signals indicate that there will be a carry at bit i only if there is a carry at bit position i-2.sup.k. For the first stage (k=0) we set: EQU G.sub.0,i=X.sub.i *Y.sub.i Eq. 14 EQU P.sub.o,i =X.sub.i +Y.sub.i Eq. 15
The designer just needs to build enough stages (k) to ensure that the CLA structure computes all of the carries. In general, only log.sub.2 (n) stages (assuming n is a power of 2) are needed so delay is related logarithmically to the bit width of the adder. The value of G.sub.i in the last stage for bit i is a carry value needed to compute a sum using the equation 1 above.
The CLA of FIG. 2 shows the carry circuitry for a four-bit carry look-ahead adder. The four blocks 20 at the bottom of FIG. 2 generate G.sub.i and P.sub.i based on equations 14 and 15 above. The remaining blocks 22 are identical to one another and perform equations 10-13. The two stages of carry tree generate the four final carry bits C.sub.0 -C.sub.3 which are used to compute the final sum bits in accordance with equation 1. The adder portion which uses X.sub.i, Y.sub.i, and C.sub.i-1 in equation 1 to generate a sum S.sub.i may optionally be incorporated in blocks 20. This CLA tree structure is easily extended to any number of bits. The speed advantages of the CLA are, of course, increased as the bit width becomes greater, while the size disadvantages of the CLA worsen as the bit width becomes greater.
The book Computer Architecture: A Quantitative Approach, previously mentioned, provides equivalent equations for a CLA adder using a different format and an equivalent CLA tree structure using an arrangement different from that shown in FIG. 2 but performing identical logic functions. FIGS. 3A, 3B, and 3C illustrate the CLA tree adder described in the above-mentioned book. The structures of FIGS. 3A-3C are presented to illustrate how a CLA structure can be implemented in a variety of ways yet still carry out the same logical functions performed by the CLA tree described with respect to equations 10-15.
FIG. 3A shows a first part of a CLA tree for an 8-bit adder, where the bits of the two numbers to be added (numbers a and b) are inputted into the top of the CLA tree into logic blocks 1. The logic functions performed by the logic blocks 1 are shown at the bottom of FIG. 3A. The outputs of the blocks 1 are input into the four input terminals of the blocks 2, performing the logic functions depicted at the bottom of FIG. 3A. The diagram of FIG. 3A would be readily understood by those skilled in the art. The diagram of FIG. 3A illustrates the generation of the various G and P values, where the G signals indicate that there will definitely be a carry bit at a particular bit position, and the P signals indicate that there will be a carry at a particular bit position only if there is a carry bit at another bit position.
FIG.3B illustrates other functions performed by the resulting CLA tree to generate carry bits, where a carry-in bit c.sub.0 is applied to the input of the CLA tree. The logic function performed by the various blocks shown in FIG. 3B is illustrated at the bottom of FIG. 3B.
FIG. 3C shows the combination of the structures shown in FIGS. 3A and 3B to form a complete CLA tree. The functions performed by each of the logic blocks A and B in FIG. 3C are illustrated at the bottom of FIG. 3C using conventional logic symbols understood by those of ordinary skill in the art.
Other CLA and carry select adder structures are described in U.S. Pat. Nos. 3,700,875; 4,764,888; 5,047,976; 5,396,445; 4,464,729; 5,122,982; 5,276,635; 5,278,783; 4,525,797; 5,283,755; and 5,027,312, all incorporated herein by reference.
Speed Versus Area Considerations
When a user of a logic synthesis tool is designing an adder in a larger circuit, the parameters which dictate the optimum adder design for the particular application include bit width, maximum tolerable delay, area constraints, input arrival time skews and other well-known considerations. If, during a timing analysis of a circuit design, it is found that the adder is too slow or too large, the adder must be changed to a different design, such as by converting a ripple adder to a carry select adder, or a carry select adder to a CLA, or vice versa. The possible choices of adders is relatively limited, and therefore the user of the logic synthesis tool is only given a choice of adder designs which do not precisely meet the user's speed vs. are requirements.
What is needed is a more flexible adder synthesis software program for developing a new adder structure which has a speed us area lying somewhere between a conventional carry select adder and a carry look-ahead adder of the same bit width.